package com.sun;

/**
 * https://leetcode.cn/problems/longest-palindromic-substring/
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */

public class Test5LongestPalindrome {
    public static void main (String[] args){
        String string = "ababa";
        String s = longestPalindrome3(string);
        System.out.println(s);
    }
    /**
     * 方法1：暴力求解发
     */
    public static String longestPalindrome1(String str){
        if (str == null || str.length() < 1){
            return "";
        }
        String res = "";
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j < str.length()+1; j++) {
                String substring = str.substring(i, j);
                StringBuffer stringBuffer = new StringBuffer(str.substring(i, j));
                stringBuffer.reverse();
                if (substring.equals(stringBuffer.toString())){
                    if (substring.length() > res.length()){
                        res = substring;
                    }
                }
            }
        }
        return res.toString();
    }

    /**
     * 方法2：中心扩散法
     */
    public static String longestPalindrome2(String str){
        if (str == null || str.length() < 1){
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < str.length(); i++) {
            int len1 = expandAroundCenter(str, i, i);
            int len2 = expandAroundCenter(str, i, i + 1);
            int len = Math.max(len1, len2);
            if(len > end - start){
                start = i - (len -1) / 2;
                end = i + len / 2;
            }
        }
        return str.substring(start,end+1);
    }

    public static int expandAroundCenter(String s, int left, int right){
        while (left >= 0 && right < s.length() &&
                s.charAt(left) == s.charAt(right)){
            --left;
            ++right;
        }
        return right - left - 1;
    }
    /**
     * 方法3：动态规划
     */
    public static String longestPalindrome3(String s){
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                int j = i + L - 1;
                System.out.println(i+","+j);
                if (j >= len) {
                    break;
                }
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        System.out.println(dp);
        return s.substring(begin, begin + maxLen);
    }
}
